/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-01
 * Time: 17:29
 */
import java.util.*;
class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length<3){
            return false;
        }
        //左边遇到合法的情况停下来
        int left = 0;
        while(left+1<arr.length&&arr[left]<arr[left+1]){
            left++;
        }
        int right = arr.length-1;
        while(right-1>=0&&arr[right]<arr[right-1]){
            right--;
        }
        if(left!=0&&right!=arr.length-1&&left==right){
            return true;
        }
        return false;
    }
}


public class TestDemo {
//    /**
//     * 在一个数组中，一个数左边比它小的数的总和，叫该数的小和
//     * 所有数的小和累加起来，叫数组小和
//     * 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：
//     * 1 4左边比4小的数：1、3 2左边比2小的数：
//     * 1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16
//     * 给定一个数组arr，求数组小和
//     */
//
//    //merge的过程
//    public static int merge(int[] arr,int left,int mid,int right){
//         //找一个数的左边比这个数小的数字，如果有将这个左边数字累加起来就是这个数的小和
//         //目的就是将每个数的小和累加起来
//        int b1 = left;
//        int e1 = mid;
//        int b2 = mid+1;
//        int e2 = right;
//        int k =0;
//        int[] tmp = new int[right-left+1];
//        int res = 0;
//        while(b1<=e1&&b2<=e2){
//            res+= arr[b1]<arr[b2] ? (right-b2+1)*arr[b1]: 0;
//            tmp[k++] = arr[b1]< arr[b2]?arr[b1++]:arr[b2++];
//        }
//        while(b1<=e1){
//            tmp[k++] = arr[b1++];
//        }
//        while(b2<=e2){
//            tmp[k++] = arr[b2++];
//        }
//        for(int i =0;i<k;++i){
//            arr[left+i] = tmp[i];
//        }
//        return res;
//    }
//
//    public static int smallSum(int[] arr,int left,int right){
//         if(left==right){
//             return 0;
//         }
//         int mid = left+((right-left)>>>1);
//
//         return smallSum(arr,left,mid)+smallSum(arr,mid+1,right)
//                 +merge(arr,left,mid,right);
//    }
//
//    public static void main1(String[] args) {
//        int[] arr = {5,2,8,3};
//        int ret = smallSum(arr,0,arr.length-1);
//        System.out.println(ret);
//    }
//
//    /**
//    * 在一个数组中，任何一个前面的数a，和任何一个后面的数b，
//    *如果(a,b)是降序的，就称为降序对 给定一个数组arr，求数组的降序对总数量
//    */
//
//    public static int merge1(int[] arr,int left,int mid,int right){
//        int b1 = left;
//        int b2 = mid+1;
//        int e1 = mid;
//        int e2 = right;
//        int[] tmp = new int[right-left+1];
//        int k = tmp.length-1;
//        int res =0;
//        // 1 2 2 2 2 3 6    1 1 1 2 3 4
//        while(e1>=b1&&e2>=b2){
//             res += arr[e1]>arr[e2] ?(e2-b2+1):0;
//             tmp[k--] = arr[e1] > arr[e2] ? arr[e1--] :arr[e2--];
//        }
//        while(e1>=b1){
//            tmp[k--] = arr[e1--];
//        }
//        while(e2>=b2){
//            tmp[k--] =  arr[e2--];
//        }
//        for(int i =0;i<tmp.length;++i){
//            arr[left+i] = tmp[i];
//        }
//        return res;
//    }
//
//    public static int possess(int[] arr,int left,int right){
//         if(left>=right){
//             return 0;
//         }
//         int mid = left + ((right-left)>>>1);
//         return possess(arr,left,mid)
//
//                 +possess(arr,mid+1,right)
//
//                 +merge1(arr,left,mid,right);
//    }
//
//    public static int reversePair(int[] arr){
//        return possess(arr,0,arr.length-1);
//    }
//
//    public static void main2(String[] args) {
//        int[] arr = {6,5,9,8,6,2};
//        // 2 + 1 + 3+ 2 + 1=9个逆序对
//        System.out.println(reversePair(arr));
//    }

    /**
     * 在一个数组中，对于任何一个数num，求有多少个(后面的数*2)依然<num，返回总个数
     * 比如：[3,1,7,0,2] 3的后面有：1，0  1的后面有：0  7的后面有：0，2   0的后面没有 2的后面没有 所以总共有5个
     */
    // 3 3 4 5 5 6   1 1 2 4 7 8 9

    public static int merge(int[] arr,int left,int mid ,int right){
        int b1 = left;
        int e1 = mid;
        int b2 = mid+1;
        int e2 = right;
        int windowR = mid+1;
        int ans =0;
        for(int i =b1;i<=e1;++i){
            while(windowR<=e2&&(long)arr[i]>(long)(2*arr[windowR])){
                windowR++;
            }
            ans += windowR-mid-1;
        }
        int[] tmp = new int[right-left+1];
        int k =0;
        while(b1<=e1&&b2<=e2){
            tmp[k++] = arr[b1]<= arr[b2]?arr[b1++]:arr[b2++];
        }
        while(b1<=e1){
            tmp[k++] = arr[b1++];
        }
        while(b2<=e2){
            tmp[k++] = arr[b2++];
        }
        for(int i =0;i<k;++i){
            arr[left+i] = tmp[i];
        }
        return ans;

    }

    public static int possess(int[] arr,int left,int right){
        if(left>=right) return 0;
        int mid = (left)+((right-left)>>>1);
        return possess(arr,left,mid)+possess(arr,mid+1,right)+
                merge(arr,left,mid,right);
    }

    public static int BiggerThanRightTwice(int[] arr){
        return possess(arr,0,arr.length-1);
    }

    public static void main(String[] args) {
        int[] arr = {2,4,3,5,1};
        System.out.println(BiggerThanRightTwice(arr));
    }
}
